﻿#include<iostream>
#include<vector>
#include<cmath>
#include<numeric>
using namespace std;

//【题目】力扣1685.有序数组中差绝对值之和
//【难度】中等
//【提交】https://leetcode.cn/problems/sum-of-absolute-differences-in-a-sorted-array/submissions/669253508/
//【标签】数组；数学；前缀和；第41场周赛
class Solution 
{
public:
    vector<int> getSumAbsoluteDifferences(vector<int>& nums) 
    {
        int n = nums.size();
        int leftsum = 0;
        int rightsum = accumulate(nums.begin(), nums.end(), 0);
        vector<int>res(n);
        for (int i = 0; i < n; i++)
        {
            rightsum -= nums[i];
            res[i] = i * nums[i] - leftsum + rightsum - (n - i - 1) * nums[i];
            leftsum += nums[i];
        }
        return res;
    }
};

/*
学习总结：
利用数组有序的特性，通过前缀和与后缀和的巧妙计算来避免暴力法的 O(n²) 复杂度，将其优化到 O(n)
将绝对值之和拆分为左右两部分：左侧为 nums[i] - nums[j] 的累加，右侧为 nums[j] - nums[i] 的累加
使用变量动态维护左累加和（leftsum）和右累加和（rightsum）
通过数学推导得到计算公式：
res[i] = i*nums[i] - leftsum + rightsum - (n-i-1)*nums[i]
在遍历过程中同步更新左右累加值，保证空间复杂度为 O(1)（不包括结果数组）

*/